#include <stdio.h>
#include <stdlib.h>

/*
	它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
	
	存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
	
	（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。


思想

	n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

	①初始状态：无序区为R[1..n]，有序区为空。
	②第1趟排序
	在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，
	
	使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

	……

	③第i趟排序
	第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中
	
	选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个
	
	数增加1个的新有序区和记录个数减少1个的新无序区。

通俗的解释

	对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。



*/

void swap(int * a, int * b)
{
  int temp;

  temp = *a;
  *a = *b;
  *b = temp;
}

void select_sort(int A[], int n)
{
  register int i, j, min, m;

  for(i = 0; i < n-1; i++) {
    min = i;//查找最小值
    for(j = i+1; j < n; j++) {
	if(A[min] > A[j]) {
	  min = j;
	}
     }

    if(min!=i)     {
      swap(&A[min],&A[i]);
      printf("第%d趟排序结果为:\n",i+1);

      for(m=0;m<n;m++)  {
	if(m>0)      {
	  printf(" ");
	}
	printf(" %d ",A[m]);
      }
      printf("\n");
    }
  }
}

int select_sort_test(void)
{
  int n;

  while(scanf("%d",&n) != EOF) {
    int i;

    int*A = (int *) malloc (sizeof(int) * n);
    for(i = 0; i < n; i++) {
      scanf("%d", &A[i]);
    }

    select_sort(A,n);

    printf("最终排序结果为:\n");
    for (i = 0; i < n; i++) {
      if(i > 0){
	printf(" ");
      }
      printf(" %d ",A[i]);
    }
    printf("\n");
  }
  return 0;
}
 
 
 
/* 版本二 */
 
#define MAX_SIZE 101
#define SWAP(x, y, t)  ((t) = (x), (x) = (y), (y) = (t))

 
void select_sort_other(int list[], int n)
{
  int i, j, min, temp;

  for (i = 0; i < n - 1; i++){
    min = i;
    for (j = i + 1; j < n; j++)
      if (list[j] < list[min])
	min = j;
    SWAP(list[i], list[min], temp);
  }
}

void select_sort_other_test(void)
{
  int i, n;
  int list[MAX_SIZE];

  printf("Enter the number of numbers to generate: ");
  scanf("%d", &n);

  if (n < 1 || n > MAX_SIZE){
    fprintf(stderr, "Improper value of n\n");
    exit(1);
  }

  for (i = 0; i < n; i++){    /* randomly generate numbers */
    list[i] = rand() * 1000;
    printf("%d ", list[i]);
  }

  select_sort_other(list, n);
  printf("\n Sorted array:\n");

  for (i = 0; i < n; i++)    /* print out sorted numbers */
    printf("%d ", list[i]);
  printf("\n");
}

int main()
{
  // select_sort_test();
  select_sort_other_test();
}
